package codingStudy.moocAlgorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author dell
 * @category 联系二叉树与递归
 */
public class bTree {

	/**
	 * 104. Maximum Depth of Binary Tree
	 * 
	 * @param root
	 * @return
	 */
	static int maximumDepthOfTree(TreeNode root) {

		int depath = 0;
		depath = maxRecursion(root);
		return depath;

	}

	static int maxRecursion(TreeNode tree) {
		if (tree == null)
			return 0;
		int left = maxRecursion(tree.left);
		int right = maxRecursion(tree.right);
		return Math.max(left, right) + 1;

	}

	/**
	 * 111. Minimum Depth of Binary Tree
	 * 
	 * @param tree
	 * @return
	 */
	static int minRecursion(TreeNode tree) {

		if (tree == null)
			return 0;
		int left = minRecursion(tree.left);
		int right = minRecursion(tree.right);
		return (left == 0 || right == 0) ? left + right + 1 : Math.min(left,
				right) + 1;

	}

	/**
	 * 226. Invert Binary Tree
	 * 
	 * @param root
	 * @return
	 */
	static TreeNode invertBinaryTree(TreeNode root) {

		return invertRecursion(root);

	}

	static TreeNode invertRecursion(TreeNode tree) {
		if (tree == null)
			return null;
		TreeNode left = invertRecursion(tree.left);
		TreeNode right = invertRecursion(tree.right);
		tree.left = right;
		tree.right = left;
		return tree;

	}

	/**
	 * 100. Same Tree
	 * 
	 * @param p
	 * @param q
	 * @return
	 */
	static boolean isSameTree(TreeNode p, TreeNode q) {

		if (p == null && q == null)
			return true;
		if (p == null || q == null)
			return false;
		if (p.val == q.val)
			return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
		else
			return false;

	}

	/**
	 * 注意递归的递归条件 112. Path Sum 判断是否存在一条路径从root到结点，包括root
	 * 
	 * @param root
	 * @param sum
	 * @return
	 */
	static boolean pathSum(TreeNode root, int sum) {

		if (root == null)
			return false;
		sum = sum - root.val;

		if (sum > 0) {
			return pathSum(root.left, sum) || pathSum(root.right, sum);
		} else if (sum < 0) {
			return false;
		} else {
			return true;
		}

	}

	/**
	 * 注意递归终止条件 112-PathSum
	 * 
	 * @param root
	 * @param sum
	 * @return
	 */
	static boolean hashPathSum(TreeNode root, int sum) {

		if (root == null)
			return false;

		// 如何改进不遍历所有叶子结点

		if (root.left == null && root.right == null)
			return root.val == sum;
		if (hashPathSum(root.left, sum - root.val))
			return true;
		if (hashPathSum(root.right, sum - root.val))
			return true;
		return false;
	}

	static List<String> hashPathSumII(TreeNode root, int sum) {
		ArrayList<String> res = new ArrayList<String>();
		if (root == null)
			return res;

		// 如何改进不遍历所有叶子结点

		if (root.left == null && root.right == null) {
			if (sum == root.val) {
				res.add(String.valueOf(root.val));
				return res;
			}
			return res;
			

		}

		List<String> lefts = hashPathSumII(root.left, sum - root.val);
		if (lefts.size() != 0) {
			for (String path : lefts) {
				res.add(String.valueOf(root.val) + "->" + path);
			}
		}
		List<String> rights = hashPathSumII(root.right, sum - root.val);
		if (rights.size() != 0) {
			for (String path : rights) {
				res.add(String.valueOf(root.val) + "->" + path);
			}
		}

		return res;
	}

	@SuppressWarnings("unused")
	private static void searchTree(TreeNode node, ArrayList<Integer> list) {
		// TODO Auto-generated method stub
		if (node == null) {
			list.add(null);
			return;
		}
		list.add(node.val);
		searchTree(node.left, list);
		searchTree(node.right, list);
	}

	private static void searchTree(TreeNode node, List<String> list, String str) {
		if (node == null)
			return;

		else {
			str = str + node.val;
			if (node.left == null && node.right == null) {
				list.add(str);
				return;
			}
		}

		searchTree(node.left, list, str);
		searchTree(node.right, list, str);
		return;
	}

	/**
	 * 257. Binary Tree Paths
	 * 
	 * @param root
	 * @return
	 */
	static List<String> binaryTreePaths(TreeNode root) {

		ArrayList<String> list = new ArrayList<String>();
		String str = "";
		searchTree(root, list, str);
		return list;

	}

	public static void main(String[] args) {
		TreeNode tree1 = new TreeNode(5);
		tree1.left = new TreeNode(4);
		tree1.right = new TreeNode(8);
		tree1.left.left = new TreeNode(11);
		tree1.right.left = new TreeNode(13);
		tree1.right.right = new TreeNode(4);
		tree1.left.left.left = new TreeNode(7);
		tree1.left.left.right = new TreeNode(2);
		tree1.right.right.left = new TreeNode(5);
		tree1.right.right.right = new TreeNode(1);
		

		List<String> res = hashPathSumII(tree1, 22);
		System.out.println(res);
	}
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}